import java.lang.reflect.Array;
import java.util.*;

class MapSum {
    HashMap<String,Integer> map;

    public MapSum() {
        map=new HashMap<>();
    }
    
    public void insert(String key, int val) {
        map.put(key,val);
    }
    
    public int sum(String prefix) {
        Set<Map.Entry<String, Integer>> entries = map.entrySet();
        int count=0;
        for (Map.Entry<String, Integer> entry : entries) {
            String key = entry.getKey();
            if (key.startsWith(prefix)){
                count+=entry.getValue();
            }
        }
        return count;
    }

//    public static void main(String[] args) {
//        System.out.println(true==true);
//    }







//    public int findPoisonedDuration(int[] timeSeries, int duration) {
//        HashSet<Integer> integers = new HashSet<>();
//
//        for (int timeSery : timeSeries) {
//            for (int i = 0; i < duration; i++) {
//                integers.add(timeSery+i);
//            }
//        }
//        return integers.size();
//
//    }

//    public static void main(String[] args) {
//        partition("a");
//        System.out.println(dft(8));
//        System.out.println(dft(7));
        //2147483647
//        System.out.println(dft(2147483647));
//        System.out.println(2147483647/2);
//        System.out.println(2147483647+1);
//    }



    public static int integerReplacement(int n) {
        return dft(n);
    }


    public static void main(String[] args) {
        int[] strings ={1,3,2,2,5,2,3,7};

        System.out.println(findLHS(strings));

    }







    //leetcode jenkins  alibaba 引入import 移除多余的
    public static int findLHS(int[] nums) {
        int count=0;
        Arrays.sort(nums);
        for (int i = 0; i < nums.length; i++) {
            int min=nums[i];
//            boolean noFlag=false;
            int countone=0;
            for (int j = i+1; j <nums.length ; j++) {
//                int countone=1;
                if (nums[j]<=min+1){
                    countone++;
                }else {
//                    noFlag=true;
                    break;
                }

            }

            if (min+1==nums[i+countone]){
                //ru
                count = count>(countone+1)?count:countone+1;
            }

        }

        return count;
    }

    private static int dft(long n) {
        if (n==1){
            return 0;
        }
        if (n%2==0){
            return 1+dft(n/2);
        }
        return 1+Math.min(dft(n+1),dft(n-1));
    }


    public static List<List<String>> partition(String s) {

        char[] chars = s.toCharArray();

        //找到每一个点回文的数量

        List<List<String>> res1 = new ArrayList<>();
        for (int i = 0; i < chars.length; i++) {
            List<String> onea = new ArrayList<>();
            for (int j = i; j <chars.length ; j++) {
                String substring = s.substring(i, j+1);
//                System.out.println(substring);
                if (isHuiWen(substring)){
                    onea.add(substring);
                }
            }
            res1.add(onea);
        }

//        System.out.println(res1);



       List<List<String>> res = new ArrayList<>();

       List<String> one = new ArrayList<>();

        List<String> strings = res1.get(0);


        dfs(res,one,0,res1,s);

        System.out.println(res);
        return res;




    }

    //dfs
    private static void dfs(List<List<String>> res, List<String> one, int start, List<List<String>> res1,String s) {
        if (start==s.length()){

            res.add(new ArrayList<>(one));
            return;
        }

        List<String> tt = res1.get(start);
        for (int i = 0; i < tt.size(); i++) {
            String s1 = tt.get(i);
            start=start+s1.length();
            one.add(s1);
            dfs(res,one,start,res1,s);
            one.remove(one.size()-1);
            start=start-s1.length();
        }
    }

    private static boolean isHuiWen(String substring) {

        char[] chars = substring.toCharArray();

        for (int i = 0; i <=chars.length/2-1; i++) {
            if (chars[i]!=chars[chars.length-1-i]){
                return false;
            }
        }
        return true;
    }


    public int findPoisonedDuration(int[] timeSeries, int duration) {
        int init=duration;

        for (int i = 1; i < timeSeries.length; i++) {
            init+=Math.min(timeSeries[i]-timeSeries[i-1],duration);
        }
        return init;
    }
    public boolean isPerfectSquare(int num) {


        int i=1;
        while (i*i<=num){
            if (i*i==num){
                return false;
            }
            i++;

        }
        return false;


    }



    public boolean detectCapitalUse(String word) {

        char[] chars = word.toCharArray();

        char aChar = chars[0];
        if (Character.isUpperCase(aChar)){

            if (word.length()>2){
                 boolean tong= Character.isUpperCase(chars[1]);
                for (int i = 2; i < chars.length; i++) {
                       if (Character.isUpperCase(chars[i])!=tong){
                            return false;
                       }
                }
            }
            return true;
        }

        for (int i = 1; i < chars.length; i++) {
            if (Character.isUpperCase(chars[i])){
                return false;
            }
        }

        return true;
    }
}